652. 寻找重复的子树

Similar Question

leading to the advanced question

Solution Tips

方案一: 序列化 + 哈希

将所有的子树序列化, 如果出现了重复的哈希值, 就说明找到了重复的子树

var findDuplicateSubtrees = function(root) {
    const seen = new Map();
    const repeat = new Set();
    const dfs = (node) => {
        if (!node) {
            return "";
        }
        let sb = '';
        sb += node.val;
        sb += "(";
        sb += dfs(node.left);
        sb += ")(";
        sb += dfs(node.right);
        sb += ")";
        if (seen.has(sb)) {
            repeat.add(seen.get(sb));
        } else {
            seen.set(sb, node);
        }
        return sb;
    }
    dfs(root);
    return [...repeat];
};

方法二: 使用三元组优化

var findDuplicateSubtrees = function(root) {
    const seen = new Map();
    const repeat = new Set();
    let idx = 0;
    const dfs = (node) => {
        if (!node) {
            return 0;
        }
        const tri = [node.val, dfs(node.left), dfs(node.right)];
        const hash = tri.toString();
        if (seen.has(hash)) {
            const pair = seen.get(hash);
            repeat.add(pair[0]);
            return pair[1];
        } else {
            seen.set(hash, [node, ++idx]);
            return idx;
        }
    }
    dfs(root);
    return [...repeat];
};